ebab7d0da53c51438720d60c6e2e467c - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Permutation pattern</title>

</head>

Permutation pattern

</h1>

</header>

In <a href="Combinatorics" title="Combinatorics">combinatorial mathematics</a> and <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a>, a (classical) permutation pattern is a sub-permutation of a longer <a href="Permutation" title="Permutation">permutation</a>. Any permutation may be written in <a href="Permutation#One-line_notation" title="Permutation">one-line notation</a> as a sequence of entries representing the result of applying the permutation to the sequence 123...; for instance the sequence 213 represents the permutation on three elements that swaps elements 1 and 2. If π and σ are two permutations represented in this way (these variable names are standard for permutations and are unrelated to the number <a href="Pi" title="Pi">pi</a>), then π is said to contain σ as a pattern if some <a href="Subsequence" title="Subsequence">subsequence</a> of the entries of π has the same relative order as all of the entries of σ.

For instance, permutation π contains the pattern 213 whenever π has three entries x, y, and z that appear within π in the order x...y...z but whose values are ordered as y < x < z, the same as the ordering of the values in the permutation 213.

The permutation 32415 on five elements contains 213 as a pattern in several different ways: 3··15, ··415, 32··5, 324··, and ·2·15 all form triples of entries with the same ordering as 213. Note that the entries do not need to be consecutive. Each of the subsequences 315, 415, 325, 324, and 215 is called a copy, instance, or occurrence of the pattern. The fact that π contains σ is written more concisely as σ ≤ π.

If a permutation π does not contain a pattern σ, then π is said to avoid σ. The permutation 51342 avoids 213; it has ten subsequences of three entries, but none of these ten subsequences has the same ordering as 213.

An international conference dedicated to permutation patterns and related topics has been held annually since 2003, called <a href="Permutation_Patterns_(conference)" title="Permutation Patterns (conference)"> Permutation Patterns</a>.

<div class="mw-heading mw-heading2"><h2 id="Early_results">Early results</h2></div>

A case can be made that <a href="Percy_MacMahon" class="mw-redirect" title="Percy MacMahon">Percy MacMahon</a> (<a href="#CITEREFMacMahon1915">1915</a>) was the first to prove a result in the field with his study of "lattice permutations".<a href="#cite_note-1">[1]</a> In particular MacMahon shows that the permutations which can be divided into two decreasing subsequences (i.e., the 123-avoiding permutations) are counted by the <a href="Catalan_number" title="Catalan number">Catalan numbers</a>.<a href="#cite_note-2">[2]</a>

Another early landmark result in the field is the <a href="Erd%C5%91s%E2%80%93Szekeres_theorem#Permutation_pattern_interpretation" title="Erdős–Szekeres theorem">Erdős–Szekeres theorem</a>; in permutation pattern language, the theorem states that for any positive integers a and b every permutation of length at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a-1)(b-1)+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a-1)(b-1)+1}</annotation>

</semantics>

</math><img src="./ff84ee2bc577e5f93cf19917444c93981998db24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.855ex; height:2.843ex;" alt="{\displaystyle (a-1)(b-1)+1}" loading="lazy"> must contain either the pattern <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1,2,3,\dots ,a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1,2,3,\dots ,a}</annotation>

</semantics>

</math><img src="./a4bb00418f882c890191f811e30bc4fa078874c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.963ex; height:2.509ex;" alt="{\displaystyle 1,2,3,\dots ,a}" loading="lazy"> or the pattern <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b,b-1,\dots ,2,1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b,b-1,\dots ,2,1}</annotation>

</semantics>

</math><img src="./ae69ee7131d809f442392c9b18ca86119526d387.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.569ex; height:2.509ex;" alt="{\displaystyle b,b-1,\dots ,2,1}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Computer_science_origins">Computer science origins</h2></div>

The study of permutation patterns began in earnest with <a href="Donald_Knuth" title="Donald Knuth">Donald Knuth</a>'s consideration of <a href="Stack-sortable_permutation" title="Stack-sortable permutation">stack-sorting</a> in 1968.<a href="#cite_note-3">[3]</a> Knuth showed that the permutation π can be sorted by a <a href="Stack_(data_structure)" class="mw-redirect" title="Stack (data structure)">stack</a> if and only if π avoids 231, and that the stack-sortable permutations are enumerated by the <a href="Catalan_number" title="Catalan number">Catalan numbers</a>.<a href="#cite_note-4">[4]</a> Knuth also raised questions about sorting with <a href="Double-ended_queue" title="Double-ended queue">deques</a>. In particular, Knuth's question asking how many permutation of n elements are obtainable with the use of a deque remains open.<a href="#cite_note-5">[5]</a> Shortly thereafter, <a href="Robert_Tarjan" title="Robert Tarjan">Robert Tarjan</a> (<a href="#CITEREFTarjan1972">1972</a>) investigated sorting by networks of stacks,<a href="#cite_note-6">[6]</a> while <a href="Vaughan_Pratt" title="Vaughan Pratt">Vaughan Pratt</a> (<a href="#CITEREFPratt1973">1973</a>) showed that the permutation π can be sorted by a deque if and only if for all k, π avoids 5,2,7,4,...,4k+1,4k−2,3,4k,1, and 5,2,7,4,...,4k+3,4k,1,4k+2,3, and every permutation that can be obtained from either of these by interchanging the last two elements or the 1 and the 2.<a href="#cite_note-pratt73-7">[7]</a> Because this collection of permutations is infinite (in fact, it is the first published example of an infinite <a href="Antichain" title="Antichain">antichain</a> of permutations), it is not immediately clear how long it takes to decide if a permutation can be sorted by a deque. <a href="#CITEREFRosenstiehlTarjan1984">Rosenstiehl & Tarjan (1984)</a> later presented a linear (in the length of π) time algorithm which determines if π can be sorted by a deque.<a href="#cite_note-8">[8]</a>

In his paper, Pratt remarked that this permutation pattern order “seems to be the only partial order on permutation that arises in a simple and natural way” and concludes by noting that “from an abstract point of view”, the permutation pattern order “is even more interesting than the networks we were characterizing”.<a href="#cite_note-pratt73-7">[7]</a>

<div class="mw-heading mw-heading2"><h2 id="Enumerative_origins">Enumerative origins</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Enumerations_of_specific_permutation_classes" title="Enumerations of specific permutation classes">Enumerations of specific permutation classes</a></div>

A prominent goal in the study of permutation patterns is in the enumeration of permutations avoiding a fixed (and typically short) permutation or set of permutations. Let Avn(B) denote the set of permutations of length n which avoid all of the permutations in the set B. (In the case B is a singleton, say {β}, the abbreviation Avn(β) is used instead.) As noted above, MacMahon and Knuth showed that |Avn(123)| = |Avn(231)| = Cn, the nth Catalan number. Thus these are isomorphic <a href="Combinatorial_class" title="Combinatorial class">combinatorial classes</a>.

<a href="#CITEREFSimionSchmidt1985">Simion & Schmidt (1985)</a> was the first paper to focus solely on enumeration. Among other results, Simion and Schmidt counted <a href="Parity_of_a_permutation" title="Parity of a permutation">even and odd permutations</a> avoiding a pattern of length three, counted permutations avoiding <a href="Enumerations_of_specific_permutation_classes#Classes_avoiding_two_patterns_of_length_3" title="Enumerations of specific permutation classes">two patterns of length three</a>, and gave the first bijective proof that 123- and 231-avoiding permutations are equinumerous.<a href="#cite_note-9">[9]</a> Since their paper, many other bijections have been given, see <a href="#CITEREFClaessonKitaev2008">Claesson & Kitaev (2008)</a> for a survey.<a href="#cite_note-10">[10]</a>

In general, if |Avn(β)| = |Avn(σ)| for all n, then β and σ are said to be <a href="Wilf_equivalence" title="Wilf equivalence">Wilf-equivalent</a>. Many Wilf-equivalences stem from the trivial fact that |Avn(β)| = |Avn(β−1)| = |Avn(βrev)| for all n, where β−1 denotes the <a href="Permutation#Product_and_inverse" title="Permutation">inverse</a> of β and βrev denotes the reverse of β. (These two operations generate the <a href="Examples_of_groups" class="mw-redirect" title="Examples of groups">Dihedral group D8</a> with a natural action on <a href="Permutation_matrices" class="mw-redirect" title="Permutation matrices">permutation matrices</a>.) However, there are also numerous examples of nontrivial Wilf-equivalences (such as that between 123 and 231):

<ul><li><a href="#CITEREFStankova1994">Stankova (1994)</a> proved that the permutations 1342 and 2413 are Wilf-equivalent.<a href="#cite_note-11">[11]</a></li>

<li><a href="#CITEREFStankovaWest2002">Stankova & West (2002)</a> proved that for any permutation β, the permutations 231 ⊕ β and 312 ⊕ β are Wilf-equivalent, where ⊕ denotes the <a href="Direct_sum_of_permutations" class="mw-redirect" title="Direct sum of permutations">direct sum</a> operation.<a href="#cite_note-12">[12]</a></li>

<li><a href="#CITEREFBackelinWestXin2007">Backelin, West & Xin (2007)</a> proved that for any permutation β and any positive integer m, the permutations 12..m ⊕ β and m...21 ⊕ β are Wilf-equivalent.<a href="#cite_note-13">[13]</a></li></ul>

From these two Wilf-equivalences and the inverse and reverse symmetries, it follows that there are three different sequences |Avn(β)| where β is of length four:

<th>sequence enumerating Avn(β)</th>

<th><a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a> reference</th>

<th>exact enumeration reference

</th></tr>

<tr>

</td></tr>

<tr>

<td><a href="#CITEREFGessel1990">Gessel (1990)</a><a href="#cite_note-gessel90-15">[15]</a>

</td></tr>

<tr>

<td>unenumerated

</td></tr></tbody></table>

In the late 1980s, <a href="Richard_P._Stanley" title="Richard P. Stanley">Richard Stanley</a> and <a href="Herbert_Wilf" title="Herbert Wilf">Herbert Wilf</a> conjectured that for every permutation β, there is some constant K such that |Avn(β)| < Kn. This was known as the <a href="Stanley%E2%80%93Wilf_conjecture" title="Stanley–Wilf conjecture">Stanley–Wilf conjecture</a> until it was proved by <a href="Adam_Marcus_(mathematician)" title="Adam Marcus (mathematician)">Adam Marcus</a> and <a href="G%C3%A1bor_Tardos" title="Gábor Tardos">Gábor Tardos</a>.<a href="#cite_note-16">[16]</a>

<div class="mw-heading mw-heading2"><h2 id="Permutation_classes">Permutation classes</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Permutation_class" title="Permutation class">Permutation class</a></div>

A permutation class, also known as a pattern class (mostly in older work), or simply a class of permutations is a <a href="Ideal_(order_theory)" title="Ideal (order theory)">downset</a> in the permutation pattern order. Every class can be defined by the minimal permutations which do not lie inside it, its basis. Thus the basis for the stack-sortable permutations is {231}, while the basis for the deque-sortable permutations is known to be infinite. The generating function for a class is Σ x|π| where the sum is taken over all permutations π in the class.

<div class="mw-heading mw-heading2"><h2 id="Möbius_function">Möbius function</h2></div>

As the set of permutations under the containment order forms a <a href="Partially_ordered_set" title="Partially ordered set">poset</a> it is natural to ask about its <a href="Incidence_algebra#Special_elements" title="Incidence algebra">Möbius function</a>, a goal first explicitly presented by <a href="#CITEREFWilf2002">Wilf (2002)</a>.<a href="#cite_note-17">[17]</a>

The goal in such investigations is to find a formula for the Möbius function of an interval [σ, π] in the permutation pattern poset which is more efficient than the naïve recursive definition. The first such result was established by <a href="#CITEREFSaganVatter2006">Sagan & Vatter (2006)</a>, who gave a formula for the Möbius function of an interval of <a href="Layered_permutation" title="Layered permutation">layered permutations</a>.<a href="#cite_note-18">[18]</a>

Later, <a href="#CITEREFBursteinJelinekJelinkovaSteingrimsson2011">Burstein et al. (2011)</a> generalized this result to intervals of <a href="Separable_permutation" title="Separable permutation">separable permutations</a>.<a href="#cite_note-19">[19]</a>

It is known that, asymptotically, at least 39.95% of all permutations π of length n satisfy μ(1, π)=0 (that is, the principal Möbius function is equal to zero),<a href="#cite_note-20">[20]</a> but for each n there exist permutations π such that μ(1, π) is an exponential function of n.<a href="#cite_note-21">[21]</a>

<div class="mw-heading mw-heading2"><h2 id="Computational_complexity">Computational complexity</h2></div>

Given a permutation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \tau }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau }</annotation>

</semantics>

</math><img src="./38a7dcde9730ef0853809fefc18d88771f95206c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.202ex; height:1.676ex;" alt="{\displaystyle \tau }" loading="lazy"> (called the text) of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> and another permutation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi }</annotation>

</semantics>

</math><img src="./9be4ba0bb8df3af72e90a0535fabcc17431e540a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.332ex; height:1.676ex;" alt="{\displaystyle \pi }" loading="lazy"> of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi }</annotation>

</semantics>

</math><img src="./9be4ba0bb8df3af72e90a0535fabcc17431e540a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.332ex; height:1.676ex;" alt="{\displaystyle \pi }" loading="lazy"> is contained in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \tau }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau }</annotation>

</semantics>

</math><img src="./38a7dcde9730ef0853809fefc18d88771f95206c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.202ex; height:1.676ex;" alt="{\displaystyle \tau }" loading="lazy">. When both <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> are regarded as variables, the problem is known to be <a href="NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a>, and the problem of counting the number of such matches is <a href="Sharp-P-complete" class="mw-redirect" title="Sharp-P-complete">#P-complete</a>.<a href="#cite_note-BBL_1998-22">[22]</a> However, PPM can be solved in <a href="Linear_time" class="mw-redirect" title="Linear time">linear time</a> when k is a constant. Indeed, Guillemot and Marx<a href="#cite_note-23">[23]</a> showed that PPM can be solved in time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{O(k^{2}\log k)}\cdot n}">

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{O(k^{2}\log k)}\cdot n}</annotation>

</semantics>

</math><img src="./dafb9935a9ee6cd2c6ec8b7a12d1c3b40fd0f87c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:12.422ex; height:3.009ex;" alt="{\displaystyle 2^{O(k^{2}\log k)}\cdot n}" loading="lazy">, meaning that it is <a href="Fixed-parameter_tractable" class="mw-redirect" title="Fixed-parameter tractable">fixed-parameter tractable</a> with respect to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

There are several variants on the PPM problem, as surveyed by Bruner and Lackner.<a href="#cite_note-24">[24]</a> For example, if the match is required to consist of contiguous entries then the problem can be solved in polynomial time.<a href="#cite_note-25">[25]</a> A different natural variant is obtained when the pattern is restricted to a proper permutation class <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy">-Pattern PPM and it was shown to be polynomial-time solvable for <a href="Separable_permutations" class="mw-redirect" title="Separable permutations">separable permutations</a>.<a href="#cite_note-BBL_1998-22">[22]</a> Later, Jelínek and Kynčl<a href="#cite_note-JK_2017-26">[26]</a> completely resolved the complexity of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mbox{Av}}(\sigma )}">

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mbox{Av}}(\sigma )}</annotation>

</semantics>

</math><img src="./e05c5444bf0bd9d8d552f8a8500c939814e90084.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.11ex; height:2.843ex;" alt="{\displaystyle {\mbox{Av}}(\sigma )}" loading="lazy">-Pattern PPM by showing that it is polynomial-time solvable when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma }</annotation>

</semantics>

</math><img src="./59f59b7c3e6fdb1d0365a494b81fb9a696138c36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle \sigma }" loading="lazy"> is equal to one of 1, 12, 21, 132, 231, 312 or 213 and NP-complete otherwise.

Another variant is when both the pattern and text are restricted to a proper permutation class <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mbox{Av}}(321)}</annotation>

</semantics>

</math><img src="./fa741166751d5d9e4bad9bf6b4cd4fd0b3b0d56d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.267ex; height:2.843ex;" alt="{\displaystyle {\mbox{Av}}(321)}" loading="lazy">-PPM could be solved in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(k^{2}n^{6})}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(k^{2}n^{6})}</annotation>

</semantics>

</math><img src="./c4c8c9bf58436186b7b166dc9717fd14cd6c64fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.297ex; height:3.176ex;" alt="{\displaystyle O(k^{2}n^{6})}" loading="lazy"> time. <a href="Michael_H._Albert" title="Michael H. Albert">Albert</a>, Lackner, Lackner, and Vatter<a href="#cite_note-28">[28]</a> later lowered this to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(kn)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(kn)}</annotation>

</semantics>

</math><img src="./6ef610f176fc2b47d4e52605ae0a86d0a16cb67f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.189ex; height:2.843ex;" alt="{\displaystyle O(kn)}" loading="lazy"> and showed that the same bound holds for the class of <a href="Skew-merged_permutation" title="Skew-merged permutation">skew-merged permutations</a>. They further asked if the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mbox{Av}}(4321)}</annotation>

</semantics>

</math><img src="./d795462a4c2bbe34861e4f2867cd92e4210b6038.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.43ex; height:2.843ex;" alt="{\displaystyle {\mbox{Av}}(4321)}" loading="lazy">-PPM is in fact NP-complete.<a href="#cite_note-JK_2017-26">[26]</a> Later, Jelínek, Opler, and Pekárek<a href="#cite_note-29">[29]</a> showed that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mbox{Av}}(\sigma )}">

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mbox{Av}}(\sigma )}</annotation>

</semantics>

</math><img src="./e05c5444bf0bd9d8d552f8a8500c939814e90084.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.11ex; height:2.843ex;" alt="{\displaystyle {\mbox{Av}}(\sigma )}" loading="lazy">-PPM is NP-complete for any <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma }</annotation>

</semantics>

</math><img src="./59f59b7c3e6fdb1d0365a494b81fb9a696138c36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle \sigma }" loading="lazy"> of length at least 4 not symmetric to one of 3412, 3142, 4213, 4123 or 41352.

<div class="mw-heading mw-heading2"><h2 id="Packing_densities">Packing densities</h2></div>

The permutation π is said to be β-optimal if no permutation of the same length as π has more copies of β. In his address to the SIAM meeting on Discrete Mathematics in 1992, Wilf defined the packing density of the permutation β of length k as

</mrow>

</munder>

<mfrac>

<mrow>

<mtext>number of copies of </mtext>

</mrow>

</mrow>

<mtext>-optimal permutation of length </mtext>

</mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lim _{n\rightarrow \infty }{\frac {{\text{number of copies of }}\beta {\text{ in a }}\beta {\text{-optimal permutation of length }}n}{\displaystyle {n \choose k}}}.}</annotation>

</semantics>

</math><img src="./6a384b330ace7ffe3a88e93d65697547abea46fd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.838ex; width:66.55ex; height:9.343ex;" alt="{\displaystyle \lim _{n\rightarrow \infty }{\frac {{\text{number of copies of }}\beta {\text{ in a }}\beta {\text{-optimal permutation of length }}n}{\displaystyle {n \choose k}}}.}" loading="lazy"></dd></dl>

An unpublished argument of <a href="Fred_Galvin" title="Fred Galvin">Fred Galvin</a> shows that the quantity inside this <a href="Limit_of_a_sequence" title="Limit of a sequence">limit</a> is nonincreasing for n ≥ k, and so the limit exists. When β is monotone, its packing density is clearly 1, and packing densities are invariant under the group of symmetries generated by inverse and reverse, so for permutations of length three, there is only one nontrivial packing density. Walter Stromquist (unpublished) settled this case by showing that the packing density of 132 is 2√3 − 3, approximately 0.46410.

For permutations β of length four, there are (due to symmetries) seven cases to consider:

<th>packing density</th>

<th>reference

</th></tr>

<tr>

<td>trivial

</td></tr>

<tr>

<td><a href="#CITEREFPrice1997">Price (1997)</a><a href="#cite_note-price97-30">[30]</a>

</td></tr>

<tr>

/* start https://en.wikipedia.org/ */

.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}

/* end https://en.wikipedia.org/ */

</style>⁠3/8⁠ = 0.375</td>

<td><a href="#CITEREFPrice1997">Price (1997)</a><a href="#cite_note-price97-30">[30]</a>

</td></tr>

<tr>

<td><a href="#CITEREFAlbertAtkinsonHandleyHolton2002">Albert et al. (2002)</a><a href="#cite_note-31">[31]</a>

</td></tr>

<tr>

<td>conjectured to be ≅ 0.244</td>

<td>

</td></tr>

<tr>

<td>conjectured to be ≅ 0.19658</td>

<td>

</td></tr>

<tr>

<td>conjectured to be ≅ 0.10474</td>

<td>

</td></tr></tbody></table>

For the three unknown permutations, there are bounds and conjectures. <a href="#CITEREFPrice1997">Price (1997)</a> used an approximation algorithm which suggests that the packing density of 1324 is around 0.244.<a href="#cite_note-price97-30">[30]</a> Birzhan Batkeyev (unpublished) constructed a family of permutations showing that the packing density of 1342 is at least the product of the packing densities of 132 and 1432, approximately 0.19658. This is conjectured to be the precise packing density of 1342. <a href="#CITEREFPresuttiStromquist2010">Presutti & Stromquist (2010)</a> provided a lower bound on the packing density of 2413. This lower bound, which can be expressed in terms of an integral, is approximately 0.10474, and conjectured to be the true packing density.<a href="#cite_note-32">[32]</a>

<div class="mw-heading mw-heading2"><h2 id="Superpatterns">Superpatterns</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Superpattern" title="Superpattern">Superpattern</a></div>

A k-superpattern is a permutation that contains all permutations of length k. For example, 25314 is a 3-superpattern because it contains all 6 permutations of length 3. It is known that k-superpatterns must have length at least k2/e2, where e ≈ 2.71828 is <a href="E_(mathematical_constant)" title="E (mathematical constant)">Euler's number</a>,<a href="#cite_note-33">[33]</a> and that there exist k-superpatterns of length ⌈(k2 + 1)/2⌉.<a href="#cite_note-engenvatter-34">[34]</a>

This upper bound is conjectured to be best possible, up to lower-order terms.<a href="#cite_note-eelw-35">[35]</a>

<div class="mw-heading mw-heading2"><h2 id="Generalizations">Generalizations</h2></div>

The type of pattern defined above, in which entries do not need to occur consecutively, is called a classical (permutation) pattern.

If the entries are required to be consecutive, then the pattern is called a consecutive pattern.

There are several ways in which the notion of "pattern" has been generalized. For example, a vincular pattern is a permutation containing dashes indicating which adjacent pairs of entries need not occur consecutively. For example, the permutation 314265 has two copies of the dashed pattern 2−31−4, given by the entries 3426 and 3425. For a dashed pattern β and any permutation π, we write β(π) for the number of copies of β in π. Thus the number of inversions in π is 2−1(π), while the number of descents is 21(π). Going further, the number of valleys in π is 213(π) + 312(π), while the number of peaks is 231(π) + 132(π). These patterns were introduced by <a href="#CITEREFBabsonSteingrímsson2000">Babson & Steingrímsson (2000)</a>, who showed that almost all known Mahonian statistics could be expressed in terms of vincular permutations.<a href="#cite_note-36">[36]</a> For example, the <a href="Major_index" title="Major index">Major index</a> of π is equal to 1−32(π) + 2−31(π) + 3−21(π) + 21(π).

Another generalization is that of a barred pattern, in which some of the entries are barred. For π to avoid the barred pattern β means that every set of entries of π which form a copy of the nonbarred entries of β can be extended to form a copy of all entries of β. <a href="#CITEREFWest1993">West (1993)</a> introduced these types of patterns in his study of permutations which could be sorted by passing them twice through a stack.<a href="#cite_note-37">[37]</a> (Note that West's definition of sorting twice through a stack is not the same as sorting with two stacks in series.) Another example of barred patterns occurs in the work of <a href="#CITEREFBousquet-MélouButler2007">Bousquet-Mélou & Butler (2007)</a>, who showed that the <a href="Schubert_variety" title="Schubert variety">Schubert variety</a> corresponding to π is <a href="Schubert_variety#Locally_factorial" title="Schubert variety">locally factorial</a> if and only if π avoids 1324 and 21354.<a href="#cite_note-38">[38]</a>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFMacMahon1915" class="citation cs2"><a href="Percy_Alexander_MacMahon" title="Percy Alexander MacMahon">MacMahon, Percy A.</a> (1915), Combinatory Analysis, London: Cambridge University Press, <a rel="nofollow" class="external text" href="https://archive.org/details/combinatoryanal01macmuoft/page/124">Volume I, Section III, Chapter V</a></cite>.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <a href="#CITEREFMacMahon1915">MacMahon (1915)</a>, Items 97 and 98.

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFKnuth1968" class="citation cs2"><a href="Donald_Knuth" title="Donald Knuth">Knuth, Donald E.</a> (1968), <a href="The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art Of Computer Programming Vol. 1</a>, Boston: Addison-Wesley, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-89683-4</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0286317">0286317</a>, <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/155842391">155842391</a></cite>.

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <a href="#CITEREFKnuth1968">Knuth (1968)</a>, Section 2.2.1, Exercises 4 and 5.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <a href="#CITEREFKnuth1968">Knuth (1968)</a>, Section 2.2.1, Exercise 13, rated M49 in the first printing, and M48 in the second.

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFTarjan1972" class="citation cs2"><a href="Robert_Tarjan" title="Robert Tarjan">Tarjan, Robert</a> (1972), "Sorting using networks of queues and stacks", <a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a>, 19 (2): 341–346, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F321694.321704">10.1145/321694.321704</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0298803">0298803</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13608929">13608929</a></cite>.

</li>

<li id="cite_note-pratt73-7">^ <a href="#cite_ref-pratt73_7-0">a</a> <a href="#cite_ref-pratt73_7-1">b</a> <cite id="CITEREFPratt1973" class="citation cs2"><a href="Vaughan_Pratt" title="Vaughan Pratt">Pratt, Vaughan R.</a> (1973), "Computing permutations with double-ended queues. Parallel stacks and parallel queues", <a href="Symposium_on_Theory_of_Computing" title="Symposium on Theory of Computing">Proc. Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973)</a>, pp. 268–277, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F800125.804058">10.1145/800125.804058</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0489115">0489115</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15740957">15740957</a></cite>.

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFRosenstiehlTarjan1984" class="citation cs2"><a href="Pierre_Rosenstiehl" title="Pierre Rosenstiehl">Rosenstiehl, Pierre</a>; <a href="Robert_Tarjan" title="Robert Tarjan">Tarjan, Robert</a> (1984), "Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations", Journal of Algorithms, 5 (3): 375–390, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0196-6774%2884%2990018-X">10.1016/0196-6774(84)90018-X</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0756164">0756164</a></cite>.

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFSimionSchmidt1985" class="citation cs2"><a href="Rodica_Simion" title="Rodica Simion">Simion, Rodica</a>; Schmidt, Frank W. (1985), "Restricted permutations", <a href="European_Journal_of_Combinatorics" title="European Journal of Combinatorics">European Journal of Combinatorics</a>, 6 (4): 383–406, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fs0195-6698%2885%2980052-4">10.1016/s0195-6698(85)80052-4</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0829358">0829358</a></cite>.

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFClaessonKitaev2008" class="citation cs2">Claesson, Anders; <a href="Sergey_Kitaev" title="Sergey Kitaev">Kitaev, Sergey</a> (2008), <a rel="nofollow" class="external text" href="https://www.mat.univie.ac.at/~slc/wpapers/s60claekit.html">"Classification of bijections between 321- and 132-avoiding permutations"</a>, <a href="S%C3%A9minaire_Lotharingien_de_Combinatoire" title="Séminaire Lotharingien de Combinatoire">Séminaire Lotharingien de Combinatoire</a>, 60: B60d, 30pp, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0805.1325">0805.1325</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2465405">2465405</a></cite>.

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFStankova1994" class="citation cs2">Stankova, Zvezdelina (1994), "Forbidden subsequences", <a href="Discrete_Mathematics_(journal)" title="Discrete Mathematics (journal)">Discrete Mathematics</a>, 132 (1–3): 291–316, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0012-365X%2894%2990242-9">10.1016/0012-365X(94)90242-9</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1297387">1297387</a></cite>.

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFStankovaWest2002" class="citation cs2">Stankova, Zvezdelina; West, Julian (2002), "A New class of Wilf-Equivalent Permutations", <a href="Journal_of_Algebraic_Combinatorics" title="Journal of Algebraic Combinatorics">Journal of Algebraic Combinatorics</a>, 15 (3): 271–290, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/math/0103152">math/0103152</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1023%2FA%3A1015016625432">10.1023/A:1015016625432</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1900628">1900628</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13921676">13921676</a></cite>.

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFBackelinWestXin2007" class="citation cs2">Backelin, Jörgen; West, Julian; Xin, Guoce (2007), "Wilf-equivalence for singleton classes", <a href="Advances_in_Applied_Mathematics" title="Advances in Applied Mathematics">Advances in Applied Mathematics</a>, 38 (2): 133–149, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.aam.2004.11.006">10.1016/j.aam.2004.11.006</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2290807">2290807</a></cite>.

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFBóna1997" class="citation cs2"><a href="Mikl%C3%B3s_B%C3%B3na" title="Miklós Bóna">Bóna, Miklós</a> (1997), "Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps", <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory</a>, Series A, 80 (2): 257–272, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/math/9702223">math/9702223</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcta.1997.2800">10.1006/jcta.1997.2800</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1485138">1485138</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:18352890">18352890</a></cite>.

</li>

<li id="cite_note-gessel90-15"><a href="#cite_ref-gessel90_15-0">^</a> <cite id="CITEREFGessel1990" class="citation cs2">Gessel, Ira M. (1990), "Symmetric functions and P-recursiveness", <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory</a>, Series A, 53 (2): 257–285, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0097-3165%2890%2990060-A">10.1016/0097-3165(90)90060-A</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1041448">1041448</a></cite>.

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite id="CITEREFMarcusTardos2004" class="citation cs2">Marcus, Adam; <a href="G%C3%A1bor_Tardos" title="Gábor Tardos">Tardos, Gábor</a> (2004), "Excluded permutation matrices and the Stanley-Wilf conjecture", <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory</a>, Series A, 107 (1): 153–160, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jcta.2004.04.002">10.1016/j.jcta.2004.04.002</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2063960">2063960</a></cite>.

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <cite id="CITEREFWilf2002" class="citation cs2"><a href="Herbert_Wilf" title="Herbert Wilf">Wilf, Herbert</a> (2002), "Patterns of permutations", <a href="Discrete_Mathematics_(journal)" title="Discrete Mathematics (journal)">Discrete Mathematics</a>, 257 (2): 575–583, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0012-365X%2802%2900515-0">10.1016/S0012-365X(02)00515-0</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1935750">1935750</a></cite>.

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite id="CITEREFSaganVatter2006" class="citation cs2"><a href="Bruce_Sagan" title="Bruce Sagan">Sagan, Bruce</a>; Vatter, Vince (2006), "The Möbius function of a composition poset", <a href="Journal_of_Algebraic_Combinatorics" title="Journal of Algebraic Combinatorics">Journal of Algebraic Combinatorics</a>, 24 (2): 117–136, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/math/0507485">math/0507485</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10801-006-0017-4">10.1007/s10801-006-0017-4</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2259013">2259013</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11283347">11283347</a></cite>.

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite id="CITEREFBursteinJelinekJelinkovaSteingrimsson2011" class="citation cs2">Burstein, Alexander; Jelinek, Vit; Jelinkova, Eva; <a href="Einar_Steingr%C3%ADmsson" title="Einar Steingrímsson">Steingrimsson, Einar</a> (2011), "The Möbius function of separable and decomposable permutations", <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory</a>, Series A, 118 (1): 2346–2364, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jcta.2011.06.002">10.1016/j.jcta.2011.06.002</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2834180">2834180</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13978488">13978488</a></cite>.

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> <cite id="CITEREFBrignallJelínekKynčlMarchant2019" class="citation cs2">Brignall, Robert; Jelínek, Vit; Kynčl, Jan; Marchant, David (2019), <a rel="nofollow" class="external text" href="http://oro.open.ac.uk/66369/1/181012-Marchant-v101.pdf">"Zeros of the Möbius function of permutations"</a> (PDF), <a href="Mathematika" title="Mathematika">Mathematika</a>, 65 (4): 1074–1092, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1810.05449">1810.05449</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1112%2FS0025579319000251">10.1112/S0025579319000251</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=3992365">3992365</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:53366318">53366318</a></cite>

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <cite id="CITEREFMarchant2020" class="citation cs2">Marchant, David (2020), "2413-balloon permutations and the growth of the Möbius function", <a href="Electronic_Journal_of_Combinatorics" title="Electronic Journal of Combinatorics">Electronic Journal of Combinatorics</a>, 27 (1): Article P1.7, 18 pp, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1812.05064">1812.05064</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.37236%2F8554">10.37236/8554</a></cite>

</li>

<li id="cite_note-BBL_1998-22">^ <a href="#cite_ref-BBL_1998_22-0">a</a> <a href="#cite_ref-BBL_1998_22-1">b</a> <cite id="CITEREFBoseBussLubiw1998" class="citation cs2"><a href="Jit_Bose" title="Jit Bose">Bose, Prosenjit</a>; Buss, Jonathan F.; <a href="Anna_Lubiw" title="Anna Lubiw">Lubiw, Anna</a> (March 1998), "Pattern matching for permutations", <a href="Information_Processing_Letters" title="Information Processing Letters">Information Processing Letters</a>, 65 (5): 277–283, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0020-0190%2897%2900209-3">10.1016/S0020-0190(97)00209-3</a></cite>

</li>

<li id="cite_note-23"><a href="#cite_ref-23">^</a> <cite id="CITEREFGuillemotMarx,_Daniel2014" class="citation journal cs1">Guillemot, Sylvain; Marx, Daniel (2014). "Finding small patterns in permutations in linear time". Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms: 20. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1307.3073">1307.3073</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F1.9781611973402.7">10.1137/1.9781611973402.7</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-61197-338-9</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1846959">1846959</a>.</cite>

</li>

<li id="cite_note-24"><a href="#cite_ref-24">^</a> <cite id="CITEREFBrunerLackner2013" class="citation cs2">Bruner, Marie-Louise; Lackner, Martin (2013), "The computational landscape of permutation patterns", Pure Mathematics and Applications, 24 (2): 83–101, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1301.0340">1301.0340</a></cite>

</li>

<li id="cite_note-25"><a href="#cite_ref-25">^</a> <cite id="CITEREFKubicaKulczyńskiRadoszewskiRytter2013" class="citation cs2">Kubica, M.; Kulczyński, T.; Radoszewski, J.; Rytter, W.; Waleń, T. (2013), "A linear time algorithm for consecutive permutation pattern matching", <a href="Information_Processing_Letters" title="Information Processing Letters">Information Processing Letters</a>, 113 (12): 430–433, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.ipl.2013.03.015">10.1016/j.ipl.2013.03.015</a></cite>

</li>

<li id="cite_note-JK_2017-26">^ <a href="#cite_ref-JK_2017_26-0">a</a> <a href="#cite_ref-JK_2017_26-1">b</a> <cite id="CITEREFJelínekKynčl2017" class="citation conference cs1">Jelínek, Vít; Kynčl, Jan (2017). "Hardness of Permutation Pattern Matching". Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19. SIAM. pp. 378–396. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1608.00529">1608.00529</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F1.9781611974782.24">10.1137/1.9781611974782.24</a>.</cite>

</li>

<li id="cite_note-27"><a href="#cite_ref-27">^</a> <cite id="CITEREFGuillemotVialette2009" class="citation cs2">Guillemot, Sylvain; Vialette, Stéphane (2009), "Pattern matching for 321-avoiding permutations", Algorithms and Computation, Lecture Notes in Computer Science, vol. 5878, pp. 1064–1073, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1511.01770">1511.01770</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-10631-6_107">10.1007/978-3-642-10631-6_107</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-10630-9</bdi></cite>

</li>

<li id="cite_note-28"><a href="#cite_ref-28">^</a> <cite id="CITEREFAlbertLacknerLacknerVatter2016" class="citation cs2"><a href="Michael_H._Albert" title="Michael H. Albert">Albert, Michael</a>; Lackner, Marie-Louise; Lackner, Martin; Vatter, Vincent (2016), "The complexity of pattern matching for 321-avoiding and skew-merged permutations", Discrete Mathematics & Theoretical Computer Science, 18 (2), <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1510.06051">1510.06051</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.46298%2Fdmtcs.1308">10.46298/dmtcs.1308</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5827603">5827603</a></cite>

</li>

<li id="cite_note-29"><a href="#cite_ref-29">^</a> <cite id="CITEREFJelínekOplerPekárek2021" class="citation conference cs1">Jelínek, Vít; Opler, Michal; Pekárek, Jakub (2021). "Griddings of Permutations and Hardness of Pattern Matching". 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, August 23-27, 2021, Tallinn, Estonia. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. pp. 65:1–65:22. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2107.10897">2107.10897</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4230%2FLIPIcs.MFCS.2021.65">10.4230/LIPIcs.MFCS.2021.65</a>.</cite>

</li>

<li id="cite_note-price97-30">^ <a href="#cite_ref-price97_30-0">a</a> <a href="#cite_ref-price97_30-1">b</a> <a href="#cite_ref-price97_30-2">c</a> <cite id="CITEREFPrice1997" class="citation cs2">Price, Alkes (1997), <a rel="nofollow" class="external text" href="https://www.proquest.com/docview/304421853">Packing densities of layered patterns</a>, Ph.D. thesis, University of Pennsylvania, <a href="ProQuest" title="ProQuest">ProQuest</a> <a rel="nofollow" class="external text" href="https://www.proquest.com/docview/304421853">304421853</a></cite>.

</li>

<li id="cite_note-31"><a href="#cite_ref-31">^</a> <cite id="CITEREFAlbertAtkinsonHandleyHolton2002" class="citation cs2"><a href="Michael_H._Albert" title="Michael H. Albert">Albert, Michael H.</a>; <a href="Michael_D._Atkinson" title="Michael D. Atkinson">Atkinson, M. D.</a>; Handley, C. C.; Holton, D. A.; Stromquist, W. (2002), <a rel="nofollow" class="external text" href="http://www.combinatorics.org/Volume_9/Abstracts/v9i1r5.html">"On packing densities of permutations"</a>, <a href="Electronic_Journal_of_Combinatorics" title="Electronic Journal of Combinatorics">Electronic Journal of Combinatorics</a>, 9: Article R5, 20 pp, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.37236%2F1622">10.37236/1622</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1887086">1887086</a></cite>.

</li>

<li id="cite_note-32"><a href="#cite_ref-32">^</a> <cite id="CITEREFPresuttiStromquist2010" class="citation cs2">Presutti, Cathleen Battiste; Stromquist, Walter (2010), <a rel="nofollow" class="external text" href="https://works.swarthmore.edu/fac-math-stat/230">"Packing rates of measures and a conjecture for the packing density of 2413"</a>, in Linton, Steve; Ruškuc, Nik; Vatter, Vincent (eds.), Permutation Patterns, London Math. Soc. Lecture Notes, vol. 376, Cambridge University Press, pp. 287–316, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FCBO9780511902499.015">10.1017/CBO9780511902499.015</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-72834-8</bdi></cite>.

</li>

<li id="cite_note-33"><a href="#cite_ref-33">^</a> <cite id="CITEREFArratia1999" class="citation cs2"><a href="Richard_Arratia" title="Richard Arratia">Arratia, Richard</a> (1999), <a rel="nofollow" class="external text" href="http://www.combinatorics.org/Volume_6/Abstracts/v6i1n1.html">"On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern"</a>, <a href="Electronic_Journal_of_Combinatorics" title="Electronic Journal of Combinatorics">Electronic Journal of Combinatorics</a>, 6: Article N1, 4 pp, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.37236%2F1477">10.37236/1477</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1710623">1710623</a></cite>.

</li>

<li id="cite_note-engenvatter-34"><a href="#cite_ref-engenvatter_34-0">^</a> <cite id="CITEREFEngenVatter2021" class="citation cs2">Engen, Michael; Vatter, Vincent (2021), "Containing all permutations", <a href="American_Mathematical_Monthly" class="mw-redirect" title="American Mathematical Monthly">American Mathematical Monthly</a>, 128 (1): 4–24, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1810.08252">1810.08252</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F00029890.2021.1835384">10.1080/00029890.2021.1835384</a></cite>

</li>

<li id="cite_note-eelw-35"><a href="#cite_ref-eelw_35-0">^</a> <cite id="CITEREFErikssonErikssonLinussonWästlund2007" class="citation cs2">Eriksson, Henrik; Eriksson, Kimmo; Linusson, Svante; Wästlund, Johan (2007), "Dense packing of patterns in a permutation", <a href="Annals_of_Combinatorics" title="Annals of Combinatorics">Annals of Combinatorics</a>, 11 (3–4): 459–470, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00026-007-0329-7">10.1007/s00026-007-0329-7</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2376116">2376116</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2021533">2021533</a></cite>.

</li>

<li id="cite_note-36"><a href="#cite_ref-36">^</a> <cite id="CITEREFBabsonSteingrímsson2000" class="citation cs2">Babson, Erik; <a href="Einar_Steingr%C3%ADmsson" title="Einar Steingrímsson">Steingrímsson, Einar</a> (2000), <a rel="nofollow" class="external text" href="http://www.emis.de/journals/SLC/wpapers/s44stein.html">"Generalized permutation patterns and a classification of the Mahonian statistics"</a>, <a href="S%C3%A9minaire_Lotharingien_de_Combinatoire" title="Séminaire Lotharingien de Combinatoire">Séminaire Lotharingien de Combinatoire</a>, 44: Research article B44b, 18 pp, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1758852">1758852</a></cite>.

</li>

<li id="cite_note-37"><a href="#cite_ref-37">^</a> <cite id="CITEREFWest1993" class="citation cs2">West, Julian (1993), "Sorting twice through a stack", <a href="Theoretical_Computer_Science_(journal)" title="Theoretical Computer Science (journal)">Theoretical Computer Science</a>, 117 (1–2): 303–313, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-3975%2893%2990321-J">10.1016/0304-3975(93)90321-J</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1235186">1235186</a></cite>.

</li>

<li id="cite_note-38"><a href="#cite_ref-38">^</a> <cite id="CITEREFBousquet-MélouButler2007" class="citation cs2"><a href="Mireille_Bousquet-M%C3%A9lou" title="Mireille Bousquet-Mélou">Bousquet-Mélou, Mireille</a>; <a href="Steve_Butler_(mathematician)" title="Steve Butler (mathematician)">Butler, Steve</a> (2007), "Forest-like permutations", <a href="Annals_of_Combinatorics" title="Annals of Combinatorics">Annals of Combinatorics</a>, 11 (3–4): 335–354, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/math/0603617">math/0603617</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00026-007-0322-1">10.1007/s00026-007-0322-1</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2376109">2376109</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:31236417">31236417</a></cite>.

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style>

<div class="side-box-text plainlist">Wikimedia Commons has media related to <a href="https://commons.wikimedia.org/wiki/Category:Permutation_patterns" class="extiw external" title="commons:Category:Permutation patterns">Permutation patterns</a>.</div></div>

</div>

<ul><li><a rel="nofollow" class="external text" href="https://www.cs.otago.ac.nz/staffpriv/malbert/permlab.php">PermLab: software for permutation patterns</a>, maintained by <a href="Michael_H._Albert" title="Michael H. Albert">Michael Albert</a>.</li>

<li><a rel="nofollow" class="external text" href="http://math.depaul.edu/~bridget/patterns.html">Database of Permutation Pattern Avoidance</a>, maintained by <a href="Bridget_Tenner" title="Bridget Tenner">Bridget Tenner</a>.</li>

<li><a rel="nofollow" class="external text" href="https://permpal.com/">PermPAL: The Permutation Pattern Avoidance Library</a>, a database of algorithmically-derived theorems about permutation classes, maintained by Christian Bean, Émile Nadeau, Jay Pantone and Henning Ulfarsson.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-25" href="https://en.wikipedia.org/wiki/?title=Permutation_pattern&oldid=1297274644">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>